package com.lw.leetcode.str.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * str
 * 809. 情感丰富的文字
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/4 17:29
 */
public class ExpressiveWords {
    public int expressiveWords(String S, String[] words) {
        RLE R = new RLE(S);
        int ans = 0;

        search:
        for (String word : words) {
            RLE R2 = new RLE(word);
            if (!R.key.equals(R2.key)) {
                continue;
            }
            for (int i = 0; i < R.counts.size(); ++i) {
                int c1 = R.counts.get(i);
                int c2 = R2.counts.get(i);
                if (c1 < 3 && c1 != c2 || c1 < c2) {
                    continue search;
                }
            }
            ans++;
        }
        return ans;
    }

    class RLE {
        String key;
        List<Integer> counts;

        public RLE(String S) {
            StringBuilder sb = new StringBuilder();
            counts = new ArrayList();

            char[] ca = S.toCharArray();
            int N = ca.length;
            int prev = -1;
            for (int i = 0; i < N; ++i) {
                if (i == N - 1 || ca[i] != ca[i + 1]) {
                    sb.append(ca[i]);
                    counts.add(i - prev);
                    prev = i;
                }
            }

            key = sb.toString();
        }
    }
}


